package sort;

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {19,27,13,22,3,1,6,5,4,2,110,65,70,98,72};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    // 原地堆排序
    public static void heapSort(int[] arr) {
        // 1.先将任意数组进行heapify调整为最大堆
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        // 2.不断交换堆顶元素到数组末尾，每交换一个元素，就有一个元素落在了最终位置
        for (int i = arr.length - 1; i > 0; i--) {
            // arr[i] 就是未排序数组的最大值，交换末尾
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 元素下沉操作
     * @param arr
     * @param i 下沉的索引
     * @param length 数组的长度
     */
    private static void siftDown(int[] arr, int i, int length) {
        while (2 * i + 1 < length) {
            int j = 2 * i + 1;
            if (j + 1 < length && arr[j + 1] > arr[j]) {
                j = j + 1;
            }
            if (arr[i] >arr[j]) {
                break;
            }else {
                swap(arr,i,j);
                i = j;
            }
        }
    }
}
